package 动态规划.背包问题;

public class _416分割等和子集 {
    /*float sum = 0;//回溯，超出时间限制！
    float count = 0;
    public boolean canPartition(int[] nums) {
        for(int num : nums){
            sum += num;
        }
        return backstack(nums,0);
    }
    public boolean backstack(int[] nums,int start){
        for(int i = start; i < nums.length; i++){
            count += nums[i];
            if(count == sum/2){
                return true;
            }else if(count < sum/2){
                boolean flag = backstack(nums,i + 1);
                if(flag == true){
                    return flag;
                }
                count -= nums[i];
            }else {
                count -= nums[i];
                continue;
            }
        }
        return false;
    }*/

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        if(sum % 2 == 1){
            return false;
        }
        int target = sum / 2;
        int[] result = new int[target + 1];
        for(int i = 0; i < nums.length; i++){
            for(int j = target; j >= nums[i]; j--){
                result[j] = Math.max(result[j],result[j - nums[i]] + nums[i]);
            }
        }
        if(result[target] == target){
            return true;
        }else{
            return false;
        }
    }
}